package string

// Problem Defination: https://www.nowcoder.com/practice/e96f1a44d4e44d9ab6289ee080099322
func isMatch(s, p string) bool {
	row, col := len(s), len(p)

	if col == 0 {
		return row == 0
	}

	dp := make([][]bool, row+1)
	for i := range dp {
		dp[i] = make([]bool, col+1)
	}

	dp[0][0] = true
	for i := 1; i < col+1 && p[i-1] == '*'; i++ {
		dp[0][i] = true
	}

	for i := 1; i <= row; i++ {
		for j := 1; j <= col; j++ {
			if p[j-1] == '*' {
				dp[i][j] = dp[i-1][j] || dp[i][j-1]
			} else if p[j-1] == '?' || s[i-1] == p[j-1] {
				dp[i][j] = dp[i-1][j-1]
			}
		}
	}

	return dp[row][col]
}

// Problem Defination: https://leetcode.cn/problems/regular-expression-matching/
func isMatch1(s, p string) bool {
	m, n := len(s), len(p)

	matches := func(i, j int) bool {
		if i == 0 {
			return false
		}
		return s[i-1] == p[j-1] || p[j-1] == '.'
	}

	dp := make([][]bool, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]bool, n+1)
	}

	dp[0][0] = true

	for i := 0; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '*' {
				// matching 0 time
				dp[i][j] = dp[i][j] || dp[i][j-2]
				if matches(i, j-1) {
					// matching multiple times
					dp[i][j] = dp[i][j] || dp[i-1][j]
				}
			} else if matches(i, j) {
				// matching 1 time
				dp[i][j] = dp[i][j] || dp[i-1][j-1]
			}
		}
	}

	return dp[m][n]
}
